using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace WindowsApplicationLZ77
{

    class ArbolHuffman
    {
        private Nodo _raiz; //NODO_RAIZ del Arbol de Huffman

        /**
         * Igual que listaFrecuencias pero en _nodos
         * sirve para armar el arbol de huffman.  
         */
        private Nodo[] _nodos = null; 
        /**
         * Cantidad de nodos del Arbol de Huffman
         */
        private int _cantidadNodos;

        public static char CODIGO_IZQUIERDA  = '0';
        public static char CODIGO_DERECHA    = '1';
        public static char NODO_SIN_CARACTER = '*';

        private bool estadoOK;

        public int CantidadNodos
        {
            get
            {
                if (_nodos == null)
                    return -1;

                return _cantidadNodos;
            }
        }

        public bool OK 
        {
            set
            {
                this.estadoOK = value;
            }

            get 
            {
                return this.estadoOK;
            }
        }

        public ArbolHuffman(Dato[] listaFrecuencias, int cant) 
        {
            this.estadoOK = false;
            this._cantidadNodos = cant;
            _nodos = new Nodo[_cantidadNodos];
            
            //Lleno _nodos
            for (int p = 0; p < _cantidadNodos; p++)
            {   //Agrego el nodo con sus hijos
                _nodos[p] = new Nodo(listaFrecuencias[p] ,null, Nodo.TipoNodo.NODO_RAIZ);
            }
            
            imprimirNodos("*** NODOS ***", _nodos);
            OrdenarNodosDeMayorAMenor();
            imprimirNodos("*** NODOS ORDENADOS ***", _nodos);

            this.OK = ArmarArbolHuffman();
        }

        internal Nodo Raiz
        {
            get { return _raiz; }
            set { _raiz = value; }
        }


        private void OrdenarNodosDeMayorAMenor()
        {
            Nodo aux = null;
            for (int i = 0; i < _nodos.Length - 1; i++)
            {
                for (int j = i + 1; j < _nodos.Length; j++)
                {
                    if (_nodos[i].Peso < _nodos[j].Peso)
                    {
                        aux = _nodos[i];
                        _nodos[i] = _nodos[j];
                        _nodos[j] = aux;
                    }
                }
            }
        }

        private void imprimirNodos(string linea, Nodo[] nodos)
        {
            System.Console.WriteLine(linea);
            for (int k = 0; k < nodos.Length; k++)
            {
                System.Console.WriteLine("N[" + k + "]=" + nodos[k].Dato.Caracter + " #" + nodos[k].Peso);
            }
        }

        #region ARMAR ARBOL DE HUFFMAN
        
        private bool ArmarArbolHuffman()
        {
            Nodo nodo0, nodo1, nodo2, raiz, posibleRaiz;
            int ultimoNodo = _nodos.Length - 1;

            if (_nodos.Length == 1)
            {
                _raiz = _nodos[0];
            }

            if (_nodos.Length == 2)
            {
                _raiz = new Nodo(new Dato(ArbolHuffman.NODO_SIN_CARACTER), null, Nodo.TipoNodo.NODO_RAIZ);
                _raiz.NodoDer = _nodos[1];
                _raiz.NodoDer.Tipo = Nodo.TipoNodo.NODO_DERECHO;

                _raiz.NodoIzq = _nodos[0];
                _raiz.NodoIzq.Tipo = Nodo.TipoNodo.NODO_IZQUIERDO;
                _raiz.Peso = _raiz.NodoDer.Peso + _raiz.NodoIzq.Peso;

                _raiz.NodoDer.Padre = _raiz;
                _raiz.NodoIzq.Padre = _raiz;
            }

            if (_nodos.Length >= 3)
            {
                //El ultimo tiene el _arbol recursivo
                nodo2 = _nodos[ultimoNodo];
                nodo1 = _nodos[ultimoNodo - 1];
                nodo0 = _nodos[ultimoNodo - 2];

                posibleRaiz = new Nodo(new Dato(ArbolHuffman.NODO_SIN_CARACTER, nodo2.Peso + nodo1.Peso), null, Nodo.TipoNodo.NODO_RAIZ);
                raiz = new Nodo(new Dato(ArbolHuffman.NODO_SIN_CARACTER, nodo0.Peso + nodo1.Peso), null, Nodo.TipoNodo.NODO_RAIZ);

                if (raiz.Peso >= posibleRaiz.Peso)
                {
                    posibleRaiz.NodoDer = nodo2;
                    posibleRaiz.NodoDer.Tipo = Nodo.TipoNodo.NODO_DERECHO;

                    posibleRaiz.NodoIzq = nodo1;
                    posibleRaiz.NodoIzq.Tipo = Nodo.TipoNodo.NODO_IZQUIERDO;

                    //Referencia al Padre
                    nodo2.Padre = posibleRaiz;
                    nodo1.Padre = posibleRaiz;

                    _nodos[ultimoNodo - 1] = posibleRaiz;
                }
                else
                {
                    raiz.NodoDer = nodo1;
                    raiz.NodoDer.Tipo = Nodo.TipoNodo.NODO_DERECHO;

                    raiz.NodoIzq = nodo0;
                    raiz.NodoIzq.Tipo = Nodo.TipoNodo.NODO_IZQUIERDO;

                    //Referencia al Padre
                    nodo1.Padre = raiz;
                    nodo0.Padre = raiz;

                    _nodos[ultimoNodo - 2] = raiz;
                    _nodos[ultimoNodo - 1] = nodo2;
                }

                eliminarUltmiosNodos(1);
                ArmarArbolHuffman();
            }

            //Supongo que el arbol esta bien armado
            return true;
        }

        private void eliminarUltmiosNodos(int cant)
        {
            int nuevaLong = _nodos.Length - cant;
            Nodo[] aux = new Nodo[nuevaLong];
            for (int i = 0; i < nuevaLong; i++)
                aux[i] = _nodos[i];

            _nodos = aux;
        }
        #endregion


        #region CODIGO DE HUFFMAN

        private static string _codigo = "";
        public static bool estadoAvanzando = false;

        public string GetCodigo(char c)
        {
            _codigo = "";
            
            string cod = GetCodigo(this.Raiz, c, true);
            
            SetearYaVisitados(_raiz , false);

            return cod;
        }

        public string GetCodigo(Nodo nodoActual, char c, bool avanzando)
        {
            //Caso base 1:
            if (nodoActual == null)
            {
                return "NO EXISTE";
            }

            //Caso base 2: Si es el _caracter buscado
            else if (nodoActual.Caracter == c)
            {
                return _codigo;
            }

            //Caso base 3: Si es una Hoja
            else if (nodoActual.NodoIzq == null && nodoActual.NodoDer == null)
            {
                _codigo = _codigo.Substring(0, _codigo.Length - 1);
                nodoActual.YaVisitado = true;
                return GetCodigo(nodoActual.Padre, c, false);
            }

            //Pruebo por el lado izquierdo.

            else if (nodoActual.NodoIzq.YaVisitado == false)
            {
                _codigo = _codigo + CODIGO_IZQUIERDA;
                return GetCodigo(nodoActual.NodoIzq, c, true);
            }

            else if (nodoActual.NodoIzq.YaVisitado == true && nodoActual.NodoDer.YaVisitado == false)
            {
                _codigo = _codigo + CODIGO_DERECHA;
                return GetCodigo(nodoActual.NodoDer, c, true);
            }

            //Avanzo por el nodo Derecho.    
            else if (nodoActual.NodoDer.YaVisitado == false)
            {
                _codigo = _codigo + CODIGO_DERECHA;
                return GetCodigo(nodoActual.NodoDer, c, true);
            }

            //Retrocedo
            else
            {
                if (_codigo.Length > 0)
                {
                    _codigo = _codigo.Substring(0, _codigo.Length - 1);
                }
                nodoActual.YaVisitado = true;
                return GetCodigo(nodoActual.Padre, c, false);
            }            

        }

        private void SetearYaVisitados(Nodo nodo, bool fueVisitado)
        {
            nodo.YaVisitado = fueVisitado;

            if (nodo.NodoIzq != null)
            {
                SetearYaVisitados(nodo.NodoIzq, false);
            }

            if (nodo.NodoDer != null)
            {
                SetearYaVisitados(nodo.NodoDer, false);
            }
        }
        

        private Nodo[] ProximoHijoSinVisitar(Nodo nodo)
        {
            Nodo[] nuevoVertice = new Nodo[1];
            if( nodo != null)
                nuevoVertice[0] = nodo.NodoDer;

            return nuevoVertice;
        }

        private bool TodosHijosVisitados(Nodo nodoActual)
        {
           return ( nodoActual.NodoIzq != null && nodoActual.NodoIzq.YaVisitado == true &&
                    nodoActual.NodoDer != null && nodoActual.NodoDer.YaVisitado == true );
        }

        private Nodo[] AgregarHijosAVertices(Nodo[] vertices, int cantidadHijos)
        {
            Nodo[] nuevosVertices = new Nodo[vertices.Length-1+cantidadHijos];
            int j = 0;
            for (int i = cantidadHijos; i < nuevosVertices.Length; i++ )
            {
                nuevosVertices[i] = vertices[j];
                j++;
            }

            //Quedan "cantidadHijos" con null al comienzo del vector
            return nuevosVertices;
        }


        public Nodo[] DropVertices(Nodo[] vertices, int cantidad) 
        {
            Nodo[] nuevoVertices = new Nodo[vertices.Length - cantidad];
            int k = cantidad;
            for (int i = 0; i < nuevoVertices.Length; i++) 
            {
                nuevoVertices[i] = vertices[k];
                k++;
            }

            return nuevoVertices;
        }
              
        #endregion


        internal Nodo[] GetNodos()
        {
            return _nodos;
        }
    }


}
